package org.example.code.test2025.one_month;

import org.example.code.test2024.eight_mouth.ListNode;
import org.example.code.test2024.eight_mouth.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Title: test0110
 * @Author yxy
 * @Package org.example.code.test2025.one_month
 * @Date 2025/1/10 09:46
 * @description:
 */
public class test0110 {

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        Map<Integer, List<Integer>> res = new HashMap<>();
        funLevelOrder(root, res, 1);
        List<Map.Entry<Integer, List<Integer>>> entryList = new ArrayList<>(res.entrySet());
        entryList.sort((a, b) -> b.getKey() - a.getKey());
        List<List<Integer>> resList = new ArrayList<>();
        for (Map.Entry<Integer, List<Integer>> entry : entryList) {
            resList.add(entry.getValue());
        }
        return resList;
    }

    private void funLevelOrder(TreeNode root, Map<Integer, List<Integer>> res, int deep) {
        if (root == null) {
            return;
        }
        res.putIfAbsent(deep, new ArrayList<>());
        res.get(deep).add(root.val);
        funLevelOrder(root.left, res, deep + 1);
        funLevelOrder(root.right, res, deep + 1);
    }

    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }

    TreeNode first = null;
    TreeNode second = null;
    TreeNode current = null;

    public void recoverTree(TreeNode root) {
        fun(root);
        if (first != null && second != null) {
            int t = first.val;
            first.val = second.val;
            second.val = t;
        }
    }

    private void fun(TreeNode root) {
        if (root == null) {
            return;
        }
        fun(root.left);
        if (current != null && root.val < current.val) {
            if (first == null) {
                first = current;
            }
            second = root;
        }
        current = root;
        fun(root.right);
    }

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        List<Integer> nums = List.of(-10, -3, 0, 5, 9);
        return buildTree(nums, 0, nums.size() - 1);
    }

    private TreeNode buildTree(List<Integer> nums, int left, int right) {
        if (left > right) {
            return null;
        }

        // 选择中间元素作为根节点
        int mid = (left + right+1)  / 2;
        TreeNode root = new TreeNode(nums.get(mid));

        // 递归构建左子树
        root.left = buildTree(nums, left, mid - 1);

        // 递归构建右子树
        root.right = buildTree(nums, mid + 1, right);

        return root;
    }

    // 中序遍历打印二叉搜索树（验证结果）
    public void inorderTraversal(TreeNode root) {
        if (root != null) {
            inorderTraversal(root.left);  // 先遍历左子树
            System.out.print(root.val + " ");  // 打印根节点
            inorderTraversal(root.right);  // 再遍历右子树
        }
    }


    public static void main(String[] args) {
        test0110 test = new test0110();
        TreeNode treeNode = test.sortedListToBST(new ListNode(1));
        test.inorderTraversal(treeNode);
    }
}
